package Hot100.BackTracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class solveNQueens {
    public static void main(String[] args) {
        System.out.println(new solveNQueens().solveNQueens(5));
    }
    List<List<String>> result = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();


    public List<List<String>> solveNQueens(int n) {
        int[][] used = new int[n][n];
        String[] answer = new String[n];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = "";
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(j == i){
                    answer[i] += "Q";
                }else {
                    answer[i] += ".";
                }

            }
        }
        for (int i = 0; i < answer.length; i++) {
            System.out.println(answer[i]);
        }
        backTracking(n,used,0,answer);
        return result;
    }
    public void backTracking(int n,int[][] used,int number,String[] answer){
        if(path.size() == n){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < n && used[number][i] == 0; i++) {
            if(isValid(used,number,i,n)){
                used[number][i] = 1;
                path.add(answer[i]);
                backTracking(n,used,number + 1,answer);
                path.removeLast();
                used[number][i] = 0;
            }
        }
    }
    public boolean isValid(int[][] used,int row,int col,int n){
        //检查同列是否有元素
        for (int i = 0; i < row; i++) {
            if(used[i][col] == 1){
                return false;
            }
        }
        //检查主对角线是否有元素
        for (int i = row - 1,j = col - 1; i >= 0 && j >= 0 ; i--,j--) {
            if(used[i][j] == 1){
                return false;
            }
        }
        //检查副对角线是否有元素
        for (int i = row - 1,j = col + 1; i >= 0 && j <n ; i--,j++) {
            if(used[i][j] == 1){
                return false;
            }
        }
        //符合条件则可以放置
        return true;
    }
}
